MOD = 10 ** 9 + 7

# 一行上所有可能的情况
line_lst = [[0, 1, 0], [0, 1, 2], [0, 2, 0], [0, 2, 1],
            [1, 0, 1], [1, 0, 2], [1, 2, 1], [1, 2, 0],
            [2, 1, 2], [2, 1, 0], [2, 0, 2], [2, 0, 1]]

# 和每一行可以相邻的行列表
near_lst = [[True] * 12 for _ in range(12)]
for i in range(12):
    for j in range(12):
        for k in range(3):
            if line_lst[i][k] == line_lst[j][k]:
                near_lst[i][j] = False
                break

# 结果缓存
CACHE = [12]

# 状态缓存（最后一个状态）
STAT = [1] * 12


class Solution:
    def numOfWays(self, n: int) -> int:
        global STAT
        global CACHE

        while len(CACHE) < n:
            nxt_stat = [0] * 12
            for i2 in range(12):
                for j2 in range(12):
                    if near_lst[i2][j2]:
                        nxt_stat[i2] += STAT[j2]
                nxt_stat[i2] %= MOD
            CACHE.append(sum(nxt_stat) % MOD)
            STAT = nxt_stat

        return CACHE[n - 1]


if __name__ == "__main__":
    print(Solution().numOfWays(1))  # 12
    print(Solution().numOfWays(2))  # 54
    print(Solution().numOfWays(3))  # 246
    print(Solution().numOfWays(7))  # 106494
    print(Solution().numOfWays(5000))  # 30228214
